/* MC202 - Estruturas de dados - 2. semestre de 2005.
 * Implementa�o de Heap para c�igo de Huffman. */

#include <stdlib.h>
#include <stdio.h>
#include "heap.h"

struct heap {
  int nelem; /* nmero de elementos no heap */
  No *vet[N_CHARS]; /* vetor de apontadores para n� da �vore de Huffman. */
};


/* Voc�deve implementar todas as fun�es abaixo. Se necess�io, voc�pode
 * criar fun�es auxiliares aqui. */
void print_heap(Heap * h){
  int c=0;
  while((c<256)&&(h->vet[c])){
    printf("[%d %d]",h->vet[c]->c,h->vet[c]->freq);
    c++;
  }
  printf("\n");
}

/* Retorna um novo Heap vazio. */
Heap *cria_heap() {
  Heap * n;
  n=calloc(1,sizeof(Heap));
  return n;
}

/* Destr� o heap passado como par�etro. */
void destroi_heap(Heap **heap) {
  free(*heap);
  *heap=NULL;
}

/* Insere o N�no heap. */
void insere_heap(Heap *heap, No *no) {
  int p=heap->nelem;
  int q;
  heap->nelem++;
  heap->vet[p]=no;
  q=(p-1)/2;
  while(p>0){
    if((heap->vet[p]->freq)*1000+heap->vet[p]->c>(heap->vet[q]->freq)*1000+heap->vet[q]->c){
      break;
    }else{
      no=heap->vet[q];
      heap->vet[q]=heap->vet[p];
      heap->vet[p]=no;
      p=q;
      q=(q-1)/2;
    }
  }
//   print_heap(heap);
}

/* Remove o menor elemento do heap, ou NULL se heap vazio. */
No *remove_menor_heap(Heap *heap) {
  No * r;
  No * aux;
  int p=0;
  int q;
  if(vazio_heap(heap)){return NULL;}
  r=heap->vet[0];
  heap->nelem--;
  heap->vet[0]=heap->vet[heap->nelem];
  heap->vet[heap->nelem]=NULL;
  q=2*p+1;
  while(q<heap->nelem){
    if((q+1!=heap->nelem)&&((heap->vet[q]->freq)*1000+heap->vet[q]->c>(heap->vet[q+1]->freq)*1000+heap->vet[q+1]->c)){
      q++;
    }
    if((heap->vet[p]->freq)*1000+heap->vet[p]->c<(heap->vet[q]->freq)*1000+heap->vet[q]->c){
      break;
    }else{
      aux=heap->vet[q];
      heap->vet[q]=heap->vet[p];
      heap->vet[p]=aux;
      p=q;
      q=2*q+1;
    }
  }
//   print_heap(heap);
  return r;
}

/* Retorna true se o heap estiver vazio, false c.c. */
boolean vazio_heap(Heap *heap) {
  if(heap->nelem){
    return false;
  }else{
    return true;
  }
}

/*BBE foi utilizado nesse programa*/
